package com.xiaolin.structure.linked.bothway;

/**
 * @ClassName BothWayLinkedList
 * @Description 双向链表
 * @Detail detail
 * @Author MyPC
 * @Date 2020/11/5
 * @Version 1.0
 */
public class BothWayLinkedList<E> {
    //链表节点个数
    int size;
    //第一个节点
    private Node<E> first;
    //最后一个节点
    private Node<E> last;

    /**
     * 连接新节点
     * @param e
     */
    private void linkElement(E e){
        //将原来的最后一个节点先存起来
        Node<E> l=last;
        //新的节点
        Node<E> newNode = new Node<>(l, e, null);
        if(l == null){
            //该链表还没有节点，将新的节点置为第一个节点,新的节点也置为最后一个节点
            this.first=newNode;
            this.last=newNode;
        }else {
            //该链表已经有了节点，旧的最后一个节点的next指向新的节点，同时将新的节点置为最后一个节点
            l.next=newNode;
            this.last=newNode;
        }
        size++;
    }

    public boolean add(E e){
        this.linkElement(e);
        return true;
    }

    /**
     * 索引校验
     * @param index
     */
    private void indexCheckout(int index){
        if( index<0 || index >= size){
            throw new IndexOutOfBoundsException("索引越界");
        }
    }

    /**
     * 根据索引获取节点
     * @param index
     * @return
     */
    private Node<E> getNode(int index){
        Node<E> out=first;
        for(int i=1;i<=index;i++){
            out=out.next;
        }
        return out;
    }

    /**
     * 根据索引获取数据,index由0开始
     * @param index
     * @return
     */
    public E get(int index){
        indexCheckout(index);
        return getNode(index).item;
    }

    /**
     * 根据索引移除元素
     * @param index
     * @return
     */
    public boolean remove(int index){
       indexCheckout(index);
        Node<E> remove = getNode(index);
        if(remove.pre == null){
            //移除的是第一个节点
            this.first=this.first.next;
            if(this.first !=null){
                //如果链表的数量大于1，则需要把新的第一个节点的前驱节点置空
                this.first.pre=null;
            }
            size--;
        }else if(remove.next == null){
            //移除的是最后一个节点
            this.last=this.last.pre;
            if(this.last !=null){
                //如果链表的数量大于1，则需要把新的最后一个节点的后继节点置空
                this.last.next=null;
            }
            size--;
        }else {
            //移除中间的一个节点
            //获取目标节点的前驱节点
            Node<E> f=remove.pre;
            //获取目标节点的后继节点
            Node<E> n=remove.next;
            f.next=n;
            n.pre=f;
            size--;
        }
        return true;
    }

    /**
     * 获取链表大小
     * @return
     */
    public int size(){
        return this.size;
    }
}

